package com.zh.note.leetcode.number;

import java.util.Arrays;

/**
 * 差分法
 */
public class Differ {
    /**
     * 差分法
     * 将指定区间内的元素都加c
     *
     * @param arr
     * @return
     */
    public static int[] differ(int[] arr, int l, int r, int c) {
        int n = arr.length;
        int[] dif = new int[n + 1];
        dif[0] = arr[0];
        /**
         * 构造差分数组
         */
        for (int i = 1; i < n; i++) {
            dif[i] = arr[i] - arr[i - 1];
        }
        insert(dif, l, r, c);
        /**
         * 还原差分数组
         */
        arr[0] = dif[0];
        for (int i = 1; i < n; i++) {
            arr[i] = arr[i - 1] + dif[i];
        }
        return arr;
    }


    private static void insert(int[] dif, int l, int r, int c) {
        if (l > r) {
            return;
        }
        dif[l] += c;
        dif[r + 1] -= c;

    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        System.out.println(Arrays.toString(differ(nums, 4, 8, 1)));
    }
}
